Elliptic curve cryptosystems rely upon the intractability of the discrete log problem in an elliptic curve over a finite field. The curve is defined by a series of points having coordinates x and y that satisfy the equation y2=x3+ax+b. Each coordinate x, y is an element of the underlying field as each point is defined by a pair of field elements. Elliptic curve operations involve addition of points which involves algorithms using both x and y coordinates of the points. However, computation of the y coordinate resulting from the addition of two points is computationally intensive.
Elliptic curve cryptosystems require point multiplications, i.e. kG which is the k-fold addition of the point G, in many operations. For example, a public key is a point multiple of a seed point P by a secret integer k, i.e. the key pair is a private key k and a public key kP. Other operations require the computation of differences of point multiples. For example, verification of a signature performed using the ECDSA requires computation of sP−eQ and so involves two point multiplications and a subtraction. Conventional point addition renders this computationally intensive.
Montgomery observed that, for some elliptic curves, the x-coordinate of the point P+Q, where + is elliptic curve addition, could be calculated from the x-coordinate of the three points P, Q and Q−P.
Using this observation, Montgomery proposed that a value for kG, i.e. the k-fold addition of G, could be obtained by computing a sequence of pairs of x-coordinates of two points P=sG and Q=(s+1)G, for appropriately selected values of s. This sequence has a property that Q−P=G and, as such, the difference of the points is known. Therefore, P+Q=(2s+1)G can be computed without using a y-coordinate. The other element of the next pair is either 2sG=2P or 2(s+1)G=2Q, either of whose x-coordinate can be computed without y-coordinates.
In Montgomery's method, the x-coordinate of the addition of two points Q1+Q2 can be computed from the x-coordinates of Q1, Q2 and Q1−Q2 as follows: Let Q1=(x1, y1) and Q2=(x2, y2) with Q1≠Q2. Now, let Q1+Q2=(x3, y3) and Q1−Q2=(x4, y4). Then, using the group law addition formulas, for curves defined over fields of characteristic two it can be verified that:
      x    3    =            x      4        +                  x        2                              x          1                +                  x          2                      +                            (                                    x              2                                                      x                1                            +                              x                2                                              )                2            .      It may be noted that a different formula is used for curves defined over a prime field. The formula for an elliptic curve y2=x3+ax+b defined over a prime field would be:
      x    3    =            -              x        4              +                  2        ⁢                  (                                    2              ⁢              b                        +                                          (                                  a                  +                                                            x                      1                                        ⁢                                          x                      2                                                                      )                            ⁢                              (                                                      x                    1                                    +                                      x                    2                                                  )                                              )                                      (                                    x              2                        -                          x              1                                )                2            
Once x3 is known, the computation may be repeated using x3 and a point that differs from x3 by a known value to compute a new x3′. Typically, where a multiple of P is required, the initial points are P and 2P with a difference of P that allows rapid reiterative computations of kP.
This technique permits the rapid computation of the x-coordinate of a point multiple. If the y-coordinate is needed in a cryptographic operation, the corresponding y-coordinate may be recovered efficiently using the technique described in U.S. Pat. No. 6,782,100.
For certain special kinds of elliptic curves, performing the above computations using only x-coordinates can be faster than other efficient implementation methods which may require computation of the corresponding y-coordinate for each point. Montgomery has defined a class of prime field curves for which not using the y-coordinate is more efficient. For non-Koblitz binary curves, there are y-free formulae that are comparable in cost with at least some other efficient implementations, such as the method of Lopez and Dahab as described in the “Guide to Elliptic Curve Cryptography”, Hankerson et al., pages 102-103.
It is frequently desirable in ECC to compute k1G1+ . . . +kdGd, using only x-coordinates, or at least mostly using only x-coordinates. Bernstein developed an algorithm for doing this when d=2. At each step, a triple of x-coordinates is computed. The three points whose x-coordinates are computed at each stage have differences of the form l1G1+l2G2 where l1, l2ε{−1, 0, 1}. Montgomery's formula may then be used once the x-coordinates of G1+G2 and G1−G2 are found using conventional addition with y-coordinates.
In some cryptographic applications, more than two scalar multiplications are performed, e.g. in batch ECC operations. However, Bernstein's algorithm does not extend beyond d=2.
It is therefore an object of the following to obviate or mitigate the above-noted disadvantages.